package com.coder.algorithm.offer_2;

import com.coder.algorithm.struct.BinaryTreeNode;

/**
 * 序列化二叉树
 *
 * @author yuhushuan
 * @date 2020/6/24 10:48
 */
public class _37_1_SerializeBinaryTrees {

    /**
     * 前序遍历序列化
     *
     * @param node
     * @param buffer
     */
    private static void serialize(BinaryTreeNode node, StringBuilder buffer) {
        if (node == null) {
            buffer.append("&,");
            return;
        }
        buffer.append(node.value).append(',');
        serialize(node.left, buffer);
        serialize(node.right, buffer);
    }

    private static BinaryTreeNode deserialize(StringBuilder builder) {
        if (builder.length() <= 0) {
            return null;
        }
        BinaryTreeNode node = parse(builder);
        if (node != null) {
            node.left = deserialize(builder);
            node.right = deserialize(builder);
        }
        return node;
    }

    private static BinaryTreeNode parse(StringBuilder builder) {
        if (builder.length() <= 0) {
            return null;
        }
        char first = builder.charAt(0);
        if (first == '&') {
            builder.delete(0, 2);
            return null;
        }
        int end = 0;
        while (builder.charAt(end) != ',') {
            end++;
        }
        int value = Integer.parseInt(builder.substring(0, end));
        builder.delete(0, end + 1);
        BinaryTreeNode node = new BinaryTreeNode();
        node.value = value;
        node.left = null;
        node.right = null;
        return node;
    }


    public static void main(String[] args) {
        // 功能测试
        // 完全二叉树
        print(BinaryTreeNode.createCompleteBinaryTree(10));
        // 只有左子树
        print(BinaryTreeNode.createOnlyLeftNodeTree(5));
        // 只有右子树
        print(BinaryTreeNode.createOnlyRightNodeTree(4));
        // 只有一个节点
        print(new BinaryTreeNode(1));
        // 所有值都相同的二叉树
        print(BinaryTreeNode.createCompleteBinaryTree(6,6));

        // 特殊输入测试
        print(null);

    }

    private static void test1() {
        BinaryTreeNode root = BinaryTreeNode.createCompleteBinaryTree(10);
        print(root);
    }

    private static void print(BinaryTreeNode root) {
        System.out.println("二叉树：");
        BinaryTreeNode.drawBinaryTree(root);
        System.out.println("前序遍历序列化：");
        StringBuilder buffer = new StringBuilder();
        serialize(root, buffer);
        System.out.println(buffer.toString());
        System.out.println("反序列化：开始");
        BinaryTreeNode tree = deserialize(buffer);
        System.out.println("反序列化：结束");
        System.out.println("反序列化后的二叉树：");
        BinaryTreeNode.drawBinaryTree(tree);
        System.out.println();
    }
}
